package string;

public class StringTest_2 {

    /**
     * 28. 实现 strStr() --easy
     * @param haystack
     * @param needle
     * @return
     */
    public int strStr(String haystack, String needle) {
/*
        直观的解法的是：枚举原串 ss 中的每个字符作为「发起点」，
        每次从原串的「发起点」和匹配串的「首位」开始尝试匹配：
        匹配成功：返回本次匹配的原串「发起点」。
        匹配失败：枚举原串的下一个「发起点」，重新尝试匹配。*/
        //整体复杂度为 O((n−m)∗m)
        if (needle.length() > haystack.length()) {
            return -1;
        }
        //这里进行一下减枝 --heystack.length() - needle.length()
        for(int i =0; i <= haystack.length() - needle.length(); i++) {
            int index1 = i,index2 = 0;
            while(index2 < needle.length() && haystack.charAt(index1) == needle.charAt(index2)) {
                index1++;
                index2++;
            }
            if(index2 == needle.length()) {
               return i;
            }
        }
        return -1;
    }


    //经典KMP算法
    //KMP算法是一种改进的字符串匹配算法，
    // 由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出，
    // 因此也被称为克努特-莫里斯-普拉特操作（简称KMP算法）。
    //O(m+n)
        /**
         * KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数，以达到快速匹配的目的。
         * 具体实现则是通过一个next()函数（或称为失配函数）来实现，该函数包含了模式串的局部匹配信息。
         * 关键在于求最长相等前后缀
         */
        // KMP 算法
        // ss: 原串(string)  pp: 匹配串(pattern)
        //前缀表（不减一）Java实现
        public int strStr_1(String haystack, String needle) {
            if (needle.length() == 0) return 0;
            int[] next = new int[needle.length()];
            getNext(next, needle);

            int j = 0;
            for (int i = 0; i < haystack.length(); i++) {
                while (j > 0 && needle.charAt(j) != haystack.charAt(i))
                    j = next[j - 1];
                if (needle.charAt(j) == haystack.charAt(i))
                    j++;
                if (j == needle.length())
                    return i - needle.length() + 1;
            }
            return -1;

        }

    private void getNext(int[] next, String s) {
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(j) != s.charAt(i))
                j = next[j - 1];
            if (s.charAt(j) == s.charAt(i))
                j++;
            next[i] = j;
        }
    }


    public static void main(String[] args) {
        StringTest_2 stringTest_2 = new StringTest_2();
        String haystack = "mississippi";
        String needle = "issip";
        int i = stringTest_2.strStr_1(haystack, needle);
        System.out.println(i);
    }
}
